El problema consiste en el procesamiento de una tabla de planes de facturación
para prefijos de números telefónicos. Para modelarlo utilizamos diccionario
implementado sobre trie que toma como clave el número de prefijo, y como
significado el nombre del plan. Cada nodo tiene punteros a diez hijos, un
puntero a string (significado) y una clave.

El algoritmo consta de 3 fases: en la primera se agregan los prefijos al
diccionario, en la segunda se comprimen los nodos que tienen a todos sus hijos
con igual plan de facturación, y en la tercera se imprimen los prefijos
resultantes del proceso.

\subsubsection*{Inserción}

Las inserciones se pueden dividir en tres casos:

\begin{enumerate}
  \item Al insertar se llega a una primer hoja, sin que tenga hijos el nodo
  donde se define el significado. En este caso se realiza la inserción ``normal''
  en el trie.

  \item Descendiendo por una rama se intenta definir un significado en un nodo
  que tiene hijos. En este caso el algoritmo debe completar todos los nodos que
  corresponda, tratando de expandirse a través de todos los hijos que no
  estén completos. Intuitivamente, se tiene un prefijo abajo en la tabla de facturación
  antigua, que es a su vez prefijo de uno ubicado con anterioridad en la misma tabla.

  \item Al descender a través de una rama correspondiente el algoritmo encuentra
  una hoja. Esto significa que ya existe un plan cuyo código es prefijo del
  que se intenta insertar, por lo tanto se cancela la operación. Esto equivale a
  que al leer la tabla antigua de arriba a abajo, leemos primero el que se leyó
  anteriormente, por lo que el que esté más abajo no será tomado en cuenta.
\end{enumerate}

\subsubsection*{Compresión}

En la segunda fase se comprime el árbol. Para poder comprimir un nodo, todos
sus hijos deben pertenecer al mismo plan de facturación. Lo chequeamos en
forma recursiva, procesando primero todos los hijos de un nodo, y luego a
él mismo. Se recorre el árbol via DFS, que retornará a un nodo el nombre
del plan que comparten sus hijos si existe uno único. Se comprime luego de
todas las inserciones, que no difiere en resultado si realizamos la compresión
a medida que se realizan las inserciones (porque si el nodo era candidato a
comprimirse estaba ya completo, y no iba a tener nuevas inserciones).
Esto hace posible cumplir con la consigna del enunciado que pide que el resultado
impreso contenga la menor cantidad de líneas posible.

\subsubsection*{Impresión por pantalla}

En la tercera y última fase se realiza la impresión de los códigos procesados,
lo que se reduce a recorrer el diccionario e imprimir todas las claves definidas
con su significado.
Para imprimir antes de los códigos el número de líneas de la nueva tabla,
mantenemos un contador de claves definidas y que no sean inválidas.
Cuando se inserta una nueva clave se la incrementa, siempre y cuando su significado
no sea ``invalid'', y al comprimir un nodo se la decrementa en nueve
(pues en ese proceso se eliminan diez hojas y se agrega una).

\subsection*{Detalles de implementación}

Dado un plan de facturación, para determinar el próximo código a insertar se
itera en el intervalo que define. Ya que puede no ser necesario agregar todos
los valores, se chequea si el siguiente código termina con `0', y tratamos
de reducir cortando el último caracter siempre que el código resultante no
contenga a un código distinto (que tiene a este como prefijo). Repetimos el
procedimiento mientras se pueda, logrando insertar al nivel más alto posible en
el árbol.

Guardamos en un {\tt set} todos los planes de facturación a procesar, lo que
simplifica la comparación y asignación de significados del diccionario,
pues se reduce a comparar y asignar punteros.

Durante la mayor parte del algoritmo tratamos a los códigos como números
enteros. Dado un plan $a-b$, $k=|b|$, definir el tamaño original del
intervalo se computa poniendo en cero los últimos $k$ dígitos de $a$,
y haciendo $a+b$. Pero un código podría tener ceros como prefijo, para
tenerlos en cuenta se lo lee primero como string, se cuenta la cantidad de
ceros al inicio, y se los agrega como prefijo al momento de imprimir el árbol.

Fue necesario utilizar {\tt long long int} para almacenar prefijos,
pues pueden tener una longitud máxima de 11 caracteres, números que no
entran en 32 bits. Debimos definir el pasaje de {\tt long long int} a {\tt char}
y viceversa.

\subsection*{Análisis de complejidad}

Sea $k$ el largo de las ramas del árbol y $t$ el número de caracteres del
alfabeto de las claves del árbol. Detallamos el orden de complejidad del
algoritmo para cada fase.

En la primera fase el algoritmo determinante es el de agregar código. En cada
inserción se debe calcular el próximo prefijo, operación cuyo orden es de $O(k)$.

La inserción normal en el trie tiene costo $O(k)$, que es la máxima cantidad
de nodos que va a atravesar.

Si se deben completar los niveles subsiguientes (el nodo que se intentaba
definir es prefijo de otro existente) se debe definir cada una de las ramas
de los hijos y explorarlas cuanto haga falta. El orden para el peor caso es
de $O(t^k)$, que está dado por la profundidad de cada rama, la cantidad
de hijos que puede tener un nodo.

Si la inserción se ve cortada (no se llega a consumir la cadena a insertar
porque se encuentra un código definido con anterioridad), el orden se puede
acotar por $O(k)$, al igual que el primero.

En la segunda fase se realiza la compresión de claves. El peor caso ocurre
cuando el diccionario está definido en todas las hojas de máxima profundidad
con un mismo plan. En ese caso se realiza un chequeo sobre cada nodo del árbol.
El orden (similarmente al caso de completar) es de $O(t^k)$.

En la tercera fase (recorrer todas las claves para imprimirlas) se debe
recorrer todos los nodos del árbol, por lo que su orden resulta también de
$O(t^k)$.

En el peor caso, dados A y B, tengo que agregar B - A claves al diccionario.
Por lo tanto, para un A y B, en peor caso se ejecuta el ciclo $(B-A)*t^k$.

Por lo tanto, la complejidad total resultante es $O(n*(max\{b-a\})*t^k + 2t^k)$, siendo
$n$ el número de líneas, $b$ y $a$ los $B$ y $A$ de cada línea correspondientemente,
y $k$ y $t$ los ya definidos.

\subsection*{Pseudocódigos}

A modo de aclaración, agregamos los pseudocódigos de los principales métodos del algoritmo:

\begin{algorithm}[H]
\linesnumbered
\caption{billing\_tables(entrada)}
\Input{archivo de entrada}
\vspace{0.4cm}

\While{existan A, B, BP que no fueron leídos de la entrada}{
	$A,B,BP \gets$ leerlo de entrada\;
	$agregar\_plan(A,B,BP)$
}
comprimir(raiz)

print(raiz)
\end{algorithm}

\begin{algorithm}[H]
\linesnumbered
\caption{agregar\_plan($A,B,BP$)}
\Input{prefijo entero $A$, B últimos números del último prefijo a agregar, nombre del plan de facturación BP}
\vspace{0.4cm}
$pj \gets$ último prefijo a agregar calculado a partir de A y B\;
$proximo \gets A$\;
$dif \gets pj - proximo + 1$\;
\While{$dif > 0$}{
	\If{último dígito de $proximo$ es cero y puedo restarle $10^{cant\_ceros\_eliminados}$ a $dif$ sin que quede negativo}{
		$proximo \gets proximo / 10$
	}\Else{
	\If{no puedo restarle $10^{cant\_ceros\_eliminados}$ a $dif$ sin que quede negativo}{
		$proximo \gets proximo \times 10$
	}}
	$cerosNuevo \gets$ cantidad de ceros a izquierda del prefijo A - digitos(proximo) - $cant\_ceros\_eliminados$\;
	$p \leftarrow$ próximo con cerosNuevo ceros agregados a izquierda\;
	$agregar(p,BP)$
}
\end{algorithm}

\begin{algorithm}[H]
\linesnumbered
\caption{agregar($p,BP$)}
\Input{prefijo $p$ a agregar, nombre del plan de facturación BP}
\vspace{0.4cm}
actual $\leftarrow$ raíz

\While{pueda bajar en el árbol}{
	actual $\leftarrow$ actual.hijo[primer caracter de p] si existe
	
	p $\leftarrow$ p sin el primer caracter
}
\If{no llegué a una hoja ya agregada}{
	\If{p es vacío}{
		completar(actual, BP)
	}
	\lElse{
		agregar la rama correspondiente a p a partir de actual
		
		$cardinal++$
	}
}
 \end{algorithm}

\begin{algorithm}[H]
\linesnumbered
\caption{completar(nodo)}
\Input{nodo del árbol}
\vspace{0.4cm}
recorrer el árbol que tiene como raíz a nodo en orden DFS, agregando hojas donde no las haya y actualizando el cardinal cada vez que lo hacemos
\end{algorithm}

\begin{algorithm}[H]
\linesnumbered
\caption{comprimir($nodo$)}
\Input{nodo del árbol}
\vspace{0.4cm}
\For{$0 < i < 9$}{
	comprimir($nodo.hijo[i]$)
}
\If{todos los hijos de nodo tienen significado y es el mismo}{

	hojasMismoBp $\leftarrow$ significado
	
	borrar hijos de nodo

	actualizar cardinal
}
\end{algorithm}
